package contest.sweek200;

import java.util.ArrayList;
import java.util.List;

/**
 * LeetCode1536. 排布二进制网格的最少交换次数
 * @author code_yc
 * @version 1.0
 * @date 2020/8/3 22:38
 */
public class Solution3 {

    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] != 0) break;
                arr[i]++;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        int ans = 0;
        // 写一个冒泡 , 每次把离当前位置最近的哪个元素抽出来，然后计算距离
        int c = n - 1;
        while (c != 0) {
            if (list.get(0) >= c) {
                list.remove(0);
            } else {
                boolean f = false;
                int i = 1;
                for (; i < list.size(); i++) {
                    if (list.get(i) >= c) {
                        f = true;
                        ans += (i - 0);
                        break;
                    }
                }
                if (!f) return -1;
                list.remove(i);
            }
            c--;
        }
        return ans;
    }
}
